//题目链接：https://leetcode.cn/problems/minimum-path-sum/
class Solution 
{
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        //dp[i][j]表示到达i，j位置的最小和，因此dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        //因为i-1，j-1,因此要处理边界条件，在原数组的左上包裹一层，且需要初始化为很大的数，保证不会影响结果
        //需要dp[1][0]=dp[0][1]=0，因为要进入通道
        dp[1][0]=dp[0][1]=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};